package array;

//求数字在排序数字中出现的次数
public class TimesOfNum {

	public static void main(String[] args) {
		TimesOfNum inNum = new TimesOfNum();
		int[] a = { 1, 2, 3, 3, 3, 3, 4, 5 };
		int k = 3;
		inNum.GetNumberOfK(a, k);
	}

	public int GetNumberOfK(int[] array, int k) {
		// 采用二分查找找出k的位置
		int position = find(array, k, 0, array.length - 1);
		int count = 0;  //出现的次数
		if (position != -1) {
			count = 1;
			//在position左边查找是否还有该元素
			for (int i = position - 1; i >= 0; i--) {
				if (array[i] == k) {
					count++;
				} else {
					break;
				}
			}
			//右边是否有
			for (int i = position + 1; i < array.length; i++) {
				if (array[i] == k) {
					count++;
				} else {
					break;
				}
			}
		}
		System.out.println(count);
		return count;
	}

	public int find(int[] array, int k, int left, int right) {
		// 如果left大于right，在二分查找的过程中表示未找到
		if (left > right) {
			return -1;
		}
		int mid = (left + right) / 2;
		if (array[mid] == k) {
			return mid;
		} else if (array[mid] < k) {
			left = mid + 1;
			find(array, k, left, right);
		} else {
			right = mid - 1;
			find(array, k, left, right);
		}
		return -1;
	}
}
